1. Field of the Invention
The present invention relates generally to computer-based printer systems and, in particular, to the prediction of the times of future events in a multi-threaded object-based graphics system, also known as a Raster Image Processor (RIP).
2. Description of the Related Art
Next generation printing systems are expected to operate at a much higher page rate than current printing systems. This is in addition to an increase in device resolution, graphics complexity, and the number of print features supported.
In computing, there is a trend toward achieving higher performance through the use of multi-processor and multi-core architectures. These architectures allow a number of threads to execute in parallel, each on a corresponding processor, thereby reducing the overall time it takes to complete a process. However, in order to take advantage of such parallelism, the processing must typically be broken down into largely independent tasks that can be executed in parallel. This is difficult to achieve for many processes, including many of the operations performed by a RIP.
The RIP process consumes a large proportion of the time required for completing a print job by a printing device. It is therefore desirable that the RIP process be accelerated through the use of multi-threading on a multi-core or multi-processor device. One method of improving printing performance is to perform the RIP process in parallel by (i) sub-dividing the input graphic objects by z order (which is an ordering of two-dimensional objects that are possibly overlapping), and (ii) rasterizing groups of graphic objects with consecutive z orders (such groups are called z bands) using separate threads executing in parallel. The outputs of all the threads can then be merged to create the final intermediate representation of the page.
In addition to rendering pixels of a page in real-time, it is advantageous to render and print consecutive pages continuously, without breaks between pages. A print engine operates best when it has a continuous stream of pages to print. If a print engine runs out of pages to print, it is said to stall. If a print engine stalls, it may firstly need to spend some time moving to an idle state. When the print engine is subsequently restarted, it may then need to spend additional time moving to a state where it is ready to print. No pages can be printed during this time, and the total print time of all pages is therefore delayed. The total print time is the time by which all pages have completed printing. Stalls can cause other problems for a print engine, including additional power usage, additional wear on print engine components, and paper waste if paper presently in the printing device's paper path needs to be discarded.
A simple method of avoiding stalls in a print engine is to buffer all pages, in either an intermediate format or as a raster images, and start the print engine after the RIP process for all pages is complete. However, this method requires a large buffer which may be costly, and total print time may be high. It is desirable that stalls in a print engine be avoided, while minimising the total print time. This is very difficult to achieve.
Various techniques in the prior art attempt to solve this problem by altering the order in which pages are processed by a RIP (which may be multi-threaded) and a renderer. For example, if complex pages that take the most time to RIP are processed first, all pages may be ready to be printed closely together in time. The likelihood of stalls is, in this case, reduced. If the duration of the RIP process for pages is estimated prior to the RIP process starting, pages can be ordered such that pages are likely to be ready to be printed by the time the print engine needs them. However, in many cases, such as when all pages are complex, it is difficult to avoid all stalls.
Other techniques in the prior art determine a time to start a print engine such that stalls are avoided and total print time is minimised. Once again, the duration of the RIP process for each page is estimated. The schedule of when and where (in a multi-threaded RIP) each page will be processed is determined based on the estimated duration of the RIP process for each page. This schedule is then used to determine the best time to start the print engine. If page RIP durations can be estimated accurately, stalls will be avoided for the most part and total print time will be minimised.
The main disadvantage of prior art methods is that many factors can cause the actual RIP duration to differ from the estimated RIP duration, including the run-time operation of the CPU and it's cache hierarchy, thread scheduling performed by an underlying operating system, and the inability to accurately estimate the RIP duration based on high-level information. This uncertainty in page RIP duration can undermine the accuracy of calculations made for avoiding print engine stalls. For example, if a page takes longer to RIP than estimated, it may not be ready for the print engine by the time the print engine is ready to receive the page. This will result in a stall in the print engine. Similarly, if a page takes less time to RIP than estimated, the print engine operation will be delayed beyond the point at which it could have commenced, and thus the minimum total print time will not be achieved.
Another disadvantage with much of the prior art is that individual pages cannot be processed in parallel. This will be particularly problematic with complex pages that take substantially longer to RIP than simple pages. The estimation of the RIP duration of complex pages that cannot be processed in parallel will be more uncertain than the estimation of the RIP duration of simple pages. Stalls in a print engine may consequently occur.